//
//  Offer_13.swift
//  LeetCode
//
//  Created by 刘彬彬 on 2021/2/26.
//  Copyright © 2021 LBB. All rights reserved.
//
//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

//输入：m = 2, n = 3, k = 1
//输出：3

//输入：m = 3, n = 1, k = 0
//输出：1
import Foundation
class Offer_13 {
    func movingCount(_ m: Int, _ n: Int, _ k: Int) -> Int {
        //已经访问的方格n
//        let visited :NSMutableArray = []
//        func dfs(_ mIndex: Int, _ nIndex: Int, _ k: Int) {
//            let locationNumber = sum(mIndex) + sum(nIndex)
//            if mIndex > m - 1 || nIndex > n - 1 || mIndex < 0 || nIndex < 0 || locationNumber > k || visited.contains([mIndex,nIndex]) {
//                return
//            }
//            visited.add([mIndex,nIndex])
//            if mIndex + 1 <= m - 1 {
//                dfs(mIndex + 1, nIndex, k)
//            }
//            if nIndex + 1 <= n - 1 {
//                dfs(mIndex, nIndex + 1, k)
//            }
//            if mIndex - 1 > 0 {
//                dfs(mIndex - 1, nIndex, k)
//            }
//            if nIndex - 1 > 0 {
//                dfs(mIndex, nIndex - 1, k)
//            }
//        }
//        dfs(0, 0, k)
        return bfs(m, n, k)
//        return visited.count
    }
    
    func bfs(_ m: Int, _ n: Int, _ k: Int) -> Int{
        var willVisitLocation = [(0,0,0,0)]
        let visited :NSMutableArray = []
        while !willVisitLocation.isEmpty {
            let (i,j,si,sj) = willVisitLocation.removeFirst()
            if i >= m || j >= n || si+sj > k || visited.contains([i,j]) {
                continue
            }
            visited.add([i,j])
            willVisitLocation.append((i+1,j,sum(i+1),sum(j)))
            willVisitLocation.append((i,j+1,sum(i),sum(j+1)))
        }
        return visited.count
    }
    
    func sum(_ num: Int) -> Int {
        var sum = 0
        var temp: Int = num
        while temp != 0 {
            sum = sum + num%10
            temp /= 10
        }
        return sum
    }
}
